SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Persistent array</title>

</head>

Persistent array

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, and more precisely regarding <a href="Data_structure" title="Data structure">data structures</a>, a persistent array is a <a href="Persistent_data_structure" title="Persistent data structure">persistent data structure</a> with properties similar to a (non-persistent) <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a>. That is, after a value's update in a persistent array, there exist two persistent arrays: one persistent array in which the update is taken into account, and one which is equal to the array before the update.

<div class="mw-heading mw-heading2"><h2 id="Difference_between_persistent_arrays_and_arrays">Difference between persistent arrays and arrays</h2></div>

An array

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {ar} =[e_{0},\dots ,e_{n-1}]}</annotation>

</semantics>

</math><img src="./11abefe5c589f71d62c967bf80ba9a173501a691.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.185ex; height:2.843ex;" alt="{\displaystyle \mathrm {ar} =[e_{0},\dots ,e_{n-1}]}" loading="lazy"> is a data structure,

with a fixed number n of elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{0},\dots ,e_{n-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{0},\dots ,e_{n-1}}</annotation>

</semantics>

</math><img src="./229df61e270f3f8c2a964a36c514f251cd9a6adc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.718ex; height:2.009ex;" alt="{\displaystyle e_{0},\dots ,e_{n-1}}" loading="lazy">. It is expected that, given the array ar and an

index <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq i<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq i<n}</annotation>

</semantics>

</math><img src="./3580bfd665087b84b88971bf567b87ab86b42871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.557ex; height:2.343ex;" alt="{\displaystyle 0\leq i<n}" loading="lazy">, the value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{i}}</annotation>

</semantics>

</math><img src="./ebdc3a9cb1583d3204eff8918b558c293e0d2cf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.883ex; height:2.009ex;" alt="{\displaystyle e_{i}}" loading="lazy"> can be

retrieved quickly. This operation is called a

lookup. Furthermore, given the array ar, an index

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq i<n}</annotation>

</semantics>

</math><img src="./3580bfd665087b84b88971bf567b87ab86b42871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.557ex; height:2.343ex;" alt="{\displaystyle 0\leq i<n}" loading="lazy"> and a new value v, a new array ar2 with

content <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]}</annotation>

</semantics>

</math><img src="./95adbea2fb090b6637b25148e5bf68c850c62427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.353ex; height:2.843ex;" alt="{\displaystyle [e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]}" loading="lazy"> can

be created quickly. This operation is called an update. The

main difference between persistent and non-persistent arrays being

that, in non-persistent arrays, the array ar is destroyed during

the creation of ar2.

For example, consider the following pseudocode.

<pre>array = [0, 0, 0]

updated_array = array.update(0, 8)

other_array = array.update(1, 3)

last_array = updated_array.update(2, 5)

</pre>

At the end of execution, the value of array is still [0, 0, 0], the

value of updated_array is [8, 0, 0], the value of other_array

is [0, 3, 0], and the value of last_array is [8, 0, 5].

There exist two kinds of persistent arrays. A persistent array may be

either partially or fully persistent. A fully persistent

array may be updated an arbitrary number of times while a partially

persistent array may be updated at most once. In our previous example,

if array were only partially persistent, the creation of

other_array would be forbidden; however, the creation of

last_array would still be valid. Indeed, updated_array is an array

distinct from array and has never been updated before the creation

of last_array.

<div class="mw-heading mw-heading2"><h2 id="Lower_Bound_on_Persistent_Array_Lookup_Time">Lower Bound on Persistent Array Lookup Time</h2></div>

Given that non-persistent arrays support both updates and lookups in constant time, it is natural to ask whether the same is possible with persistent arrays. The following theorem shows that under mild assumptions about the space complexity of the array, lookups must take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\log \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (\log \log n)}</annotation>

</semantics>

</math><img src="./abd3ed358ca0ff406e846ab34eacde0685b93373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.6ex; height:2.843ex;" alt="{\displaystyle \Omega (\log \log n)}" loading="lazy"> time in the worst case, regardless of update time, in the <a href="Cell-probe_model" title="Cell-probe model">cell-probe model</a>.

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

Theorem<a href="#cite_note-Straka-1">[1]</a>: 67–69 —Consider a partially persistent array with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=n^{\gamma }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=n^{\gamma }}</annotation>

</semantics>

</math><img src="./f0614a02a1cdc1c27136cf31e5ededbd246de82c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.658ex; height:2.343ex;" alt="{\displaystyle m=n^{\gamma }}" loading="lazy"> modifications, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy"> is a constant fulfilling <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1<\gamma \leq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1<\gamma \leq 2}</annotation>

</semantics>

</math><img src="./985a6fb8352d5ae252140a0e60773635669a0b1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.784ex; height:2.676ex;" alt="{\displaystyle 1<\gamma \leq 2}" loading="lazy">.

Assuming the space complexity of the array is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m\log ^{k}m)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m\log ^{k}m)}</annotation>

</semantics>

</math><img src="./5bee4056573bcd8bd139e8f1b0743b61c2359e42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.498ex; height:3.176ex;" alt="{\displaystyle O(m\log ^{k}m)}" loading="lazy"> for a constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">,

the lower bound on the lookup complexity in this partially persistent

array is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\log \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (\log \log n)}</annotation>

</semantics>

</math><img src="./abd3ed358ca0ff406e846ab34eacde0685b93373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.6ex; height:2.843ex;" alt="{\displaystyle \Omega (\log \log n)}" loading="lazy">.

</div>

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

In this section, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the number of elements of the array, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is the number of updates.

<div class="mw-heading mw-heading3"><h3 id="Worst_case_log-time">Worst case log-time</h3></div>

The most straightforward implementation of a fully persistent array uses an arbitrary persistent map, whose keys are the numbers from 0 to n − 1. A persistent map may be implemented using a persistent <a href="Balanced_tree" class="mw-redirect" title="Balanced tree">balanced tree</a>, in which case both updates and lookups would take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> time. This implementation is optimal for the <a href="Pointer_machine" title="Pointer machine">pointer machine</a> model.<a href="#cite_note-Straka-1">[1]</a>: 88–89

<div class="mw-heading mw-heading3"><h3 id="Shallow_binding">Shallow binding</h3></div>

A fully persistent array may be implemented using an array and the

so-called Baker's trick.<a href="#cite_note-ML-2">[2]</a> This implementation is used in the <a href="OCaml" title="OCaml">OCaml</a> module parray.ml<a href="#cite_note-3">[3]</a> by Jean-Christophe Filliâtre.

In order to define this implementation, a few other definitions must

be given. An initial array is an array that is not generated by

an update on another array. A child of an array ar is an

array of the form ar.update(i,v), and ar is the parent

of ar.update(i,v). A descendant of an array ar is either

ar or the descendant of a child of ar. The initial array

of an array ar is either ar if ar is initial, or it is the

initial array of the parent of ar. That is, the initial array of

ar is the unique array init such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})}</annotation>

</semantics>

</math><img src="./2a2a900175d2b791e01cd12b248732b8c4e2ca5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.965ex; height:2.843ex;" alt="{\displaystyle \mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})}" loading="lazy">, with init initial

and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{0},\dots ,i_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{0},\dots ,i_{m}}</annotation>

</semantics>

</math><img src="./aef8cc15c80afc053851505c44765e77bd3ddee1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.512ex; height:2.509ex;" alt="{\displaystyle i_{0},\dots ,i_{m}}" loading="lazy"> an arbitrary sequence of indexes and

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{0},\dots ,v_{m}}</annotation>

</semantics>

</math><img src="./63973dac99ac1bc4fe0b24b5b028b9d16acd1d96.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.163ex; height:2.009ex;" alt="{\displaystyle v_{0},\dots ,v_{m}}" loading="lazy"> an arbitrary sequence of value. A

family of arrays is thus a set of arrays containing an initial

array and all of its descendants. Finally, the tree of a family of

arrays is the <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree</a> whose nodes are the

arrays, and with an edge e from ar to each of its children

ar.update(i,v).

A persistent array using Baker's trick consists of a pair with

an actual array called array and the tree of arrays. This tree

admits an arbitrary root - not necessarily the initial array. The

root may be moved to an arbitrary node of the tree. Changing the root

from root to an arbitrary node ar takes time proportional to

the depth of ar. That is, in the distance between root and

ar. Similarly, looking up a value takes time proportional to the

distance between the array and the root of its family. Thus, if the

same array ar may be lookup multiple times, it is more efficient

to move the root to ar before doing the lookup. Finally updating

an array only takes <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a>.

Technically, given two adjacent arrays ar1 and ar2, with

ar1 closer to the root than ar2, the edge from ar1 to

ar2 is labelled by (i,ar2[i]), where i the only position

whose value differ between ar1 and ar2.

Accessing an element i of an array ar is done as follows. If

ar is the root, then ar[i] equals root[i]. Otherwise, let

e the edge leaving ar toward the root. If the label of e

is (i,v) then ar[i] equals v. Otherwise, let ar2 be

the other node of the edge e. Then ar[i] equals

ar2[i]. The computation of ar2[i] is done recursively using

the same definition.

The creation of ar.update(i,v) consists in adding a new node

ar2 to the tree, and an edge e from ar to ar2 labelled

by (i,v).

Finally, moving the root to a node ar is done as follows. If

ar is already the root, there is nothing to do. Otherwise, let

e the edge leaving ar toward the current root, (i,v) its

label and ar2 the other end of e. Moving the root to ar is

done by first moving the root to ar2, changing the label of e

to (i, ar2[i]), and changing array[i] to v.

Updates take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> time. Lookups take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> time if the root is the array being looked up, but <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (m)}</annotation>

</semantics>

</math><img src="./80a5cb7e7794c6e0c32bbed3e25c64f1c22a1a57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.658ex; height:2.843ex;" alt="{\displaystyle \Theta (m)}" loading="lazy"> time in the worst case.

<div class="mw-heading mw-heading3"><h3 id="Expected_amortized_log-log-time">Expected amortized log-log-time</h3></div>

In 1989, Dietz<a href="#cite_note-Dietz-4">[4]</a>

gave an implementation of fully persistent arrays using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m+n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m+n)}</annotation>

</semantics>

</math><img src="./0922aa919079469e54e4c3affe9b7ab456f1a124.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.858ex; height:2.843ex;" alt="{\displaystyle O(m+n)}" loading="lazy"> space such that lookups can be done in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log m)}</annotation>

</semantics>

</math><img src="./541113a51c1eaff2598b6e7d8044360d64391ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.341ex; height:2.843ex;" alt="{\displaystyle O(\log \log m)}" loading="lazy"> worst-case time, and updates can be done in

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log m)}</annotation>

</semantics>

</math><img src="./541113a51c1eaff2598b6e7d8044360d64391ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.341ex; height:2.843ex;" alt="{\displaystyle O(\log \log m)}" loading="lazy"> expected amortized time. By the lower bound from the previous section, this time complexity for lookup is optimal when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=n^{\gamma }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=n^{\gamma }}</annotation>

</semantics>

</math><img src="./f0614a02a1cdc1c27136cf31e5ededbd246de82c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.658ex; height:2.343ex;" alt="{\displaystyle m=n^{\gamma }}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma \in (1,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma \in (1,2]}</annotation>

</semantics>

</math><img src="./e5ea13cdfbf327c0dcbd99c790aa74091c4e0d54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.013ex; height:2.843ex;" alt="{\displaystyle \gamma \in (1,2]}" loading="lazy">. This implementation is related to the <a href="Order-maintenance_problem" title="Order-maintenance problem">order-maintenance problem</a> and involves <a href="VEB_tree" class="mw-redirect" title="VEB tree">vEB trees</a>, one for the entire array and one for each index.

Straka showed that the times for both operations can be (slightly) improved to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log \min(m,n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log \min(m,n))}</annotation>

</semantics>

</math><img src="./a452b0b42b748c0fc94557dfd5b3ccabf3c74a0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.454ex; height:2.843ex;" alt="{\displaystyle O(\log \log \min(m,n))}" loading="lazy">.<a href="#cite_note-Straka-1">[1]</a>: 88–89

<div class="mw-heading mw-heading3"><h3 id="Worst_case_log-log-time">Worst case log-log-time</h3></div>

Straka showed how to achieve <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O((\log \log m)^{2}/\log \log \log m)}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O((\log \log m)^{2}/\log \log \log m)}</annotation>

</semantics>

</math><img src="./464e516e309e9d98b0302a040c65f65cd03e3e94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.871ex; height:3.176ex;" alt="{\displaystyle O((\log \log m)^{2}/\log \log \log m)}" loading="lazy"> worst-case time and linear (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m+n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m+n)}</annotation>

</semantics>

</math><img src="./0922aa919079469e54e4c3affe9b7ab456f1a124.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.858ex; height:2.843ex;" alt="{\displaystyle O(m+n)}" loading="lazy">) space, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log m)}</annotation>

</semantics>

</math><img src="./541113a51c1eaff2598b6e7d8044360d64391ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.341ex; height:2.843ex;" alt="{\displaystyle O(\log \log m)}" loading="lazy"> worst-case time and super-linear space. It remains open whether it is possible to achieve worst-case time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log m)}</annotation>

</semantics>

</math><img src="./541113a51c1eaff2598b6e7d8044360d64391ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.341ex; height:2.843ex;" alt="{\displaystyle O(\log \log m)}" loading="lazy"> subject to linear space.<a href="#cite_note-Straka-1">[1]</a>: 88

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFStraka_e2013" class="citation book cs1">Straka e, Milan (2013). Functional Data Structures and Algorithms. Prague.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: location missing publisher (link)

</li>

<li id="cite_note-ML-2"><a href="#cite_ref-ML_2-0">^</a> <cite id="CITEREFFillâtreConchon2007" class="citation book cs1">Fillâtre, Jean-Christophe; Conchon, Sylvain (2007). <a rel="nofollow" class="external text" href="https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf">A Persistent Union-find Data Structure</a> (PDF). New York, NY, USA: ACM. pp. 37–46. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-59593-676-9</bdi>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFFilliâtre" class="citation web cs1">Filliâtre, Jean-Christophe. <a rel="nofollow" class="external text" href="https://github.com/backtracking/ocaml-bazaar/blob/main/parray.ml">"Persistent-array implementation"</a>. <a href="GitHub" title="GitHub">GitHub</a>.</cite>

</li>

<li id="cite_note-Dietz-4"><a href="#cite_ref-Dietz_4-0">^</a> <cite id="CITEREFDietz1989" class="citation conference cs1">Dietz, Paul F. (1989). "Fully persistent arrays". Proceedings of the Algorithms and Data Structures. pp. 67–74. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.621.1599">10.1.1.621.1599</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-51542-9_8">10.1007/3-540-51542-9_8</a>.</cite>

</li>

</ol></div></div>.</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-05" href="https://en.wikipedia.org/wiki/?title=Persistent_array&oldid=1304333723">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>